package com.gxc.graph;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 普里姆算法
 * 1)以某一个点开始，寻找当前该点可以访问的所有的边；
 2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
 3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；
 4）此时由所有边构成的树即为最小生成树。
 */
public class Prim {

    public static void main(String[] args) {
        Graph graph = BreadthFirst.createGraph();

        Set<Edge> set = prim(graph);
    }

    private static Set<Edge> prim(Graph graph) {
        PriorityQueue<Edge> queue = new PriorityQueue(new EdgeComparator());
        
        Set<Node> existNode = new HashSet<>();
        Set<Edge> result = new HashSet<>();

        for (Node node : graph.nodes.values()) {//图是森林的问题
            if (!existNode.contains(node)) {
                existNode.add(node);
                for (Edge edge : node.edges) {//由一个点解锁所有的边
                    queue.add(edge);
                }
                while (!queue.isEmpty()) {
                    Edge edge = queue.poll();
                    if (!existNode.contains(edge.to)) {//不含有的时候则是新的点
                        result.add(edge);
                        existNode.add(edge.to);

                        for (Edge edge1 : edge.to.edges) {
                            queue.add(edge1);
                        }
                    }
                }
            }
        }
        return result;
    }

    public static class EdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight-o2.weight;
        }
    }

}
